package leetcode.linkedlist.reverse;

import leetcode.linkedlist.ListNode;

/**
 * 206. 反转链表
 *
 */
public class ReverseList {

    public static void main(String[] args) {
        ReverseList solution = new ReverseList();
        Integer[] arr1 = {1, 2, 3, 4, 5};
        ListNode l1 = ListNode.makeLinkedList(arr1);

        ListNode resList = solution.reverseList(l1);
        System.out.println(resList.list());
    }


    /**
     * 递归实现
     *
     * 利用每一个栈帧中的节点实现链表的反转, 先递归, 再利用递归方法的参数进行逻辑操作
     *
     * @param head  链表头节点
     * @return      右边已经反转好的链表的头节点(其实就是原始链表的尾节点), 每次递归函数的返回结果都一样
     */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 递归函数的返回值(原始链表的尾节点)不参与处理, 只作为结果返回
        ListNode newHead = reverseList(head.next);

        // head -> node <- node <- node
        // head节点之后的链表已经完成了反转

        // 使用当前栈中的方法参数(依次遍历的节点)实现当前节点的反转
        head.next.next = head;
        // 反转之后, 当前节点的next指针置空, 是为了原始链表的头节点的next为null
        head.next = null;
        return newHead;
    }


    /**
     * 双指针 迭代遍历
     *
     * @param head 头节点
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

}
